package com.nanbei.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ClassDescription: 最小生成树 Prim 算法
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/2 16:45
 */
public class Prim {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");
        Vertex v7 = new Vertex("v7");

        v1.setEdges(Arrays.asList(new Edge(v2, 2), new Edge(v3, 4), new Edge(v4, 1)));
        v2.setEdges(Arrays.asList(new Edge(v1, 2), new Edge(v4, 3), new Edge(v5, 10)));
        v3.setEdges(Arrays.asList(new Edge(v1, 4), new Edge(v4, 2), new Edge(v6, 5)));
        v4.setEdges(Arrays.asList(new Edge(v1, 1), new Edge(v2, 3), new Edge(v3, 2),
                new Edge(v5, 7), new Edge(v6, 8), new Edge(v7, 4)));
        v5.setEdges(Arrays.asList(new Edge(v2, 10), new Edge(v4, 7), new Edge(v7, 6)));
        v6.setEdges(Arrays.asList(new Edge(v3, 5), new Edge(v4, 8), new Edge(v7, 1)));
        v7.setEdges(Arrays.asList(new Edge(v4, 4), new Edge(v5, 6), new Edge(v6, 1)));

        List<Vertex> graph = Arrays.asList(v1, v2, v3, v4, v5, v6, v7);

        prim(graph, v1);

    }

    private static void prim(List<Vertex> vertexList, Vertex v) {
        ArrayList<Vertex> graph = new ArrayList<>(vertexList);
        v.setDist(0);
        while (!graph.isEmpty()){
            // 每次选择最小临时距离的未访问顶点，作为新的当前顶点
            Vertex vertex = findMinVertex(graph);
            // 对于当前顶点，遍历其所有未访问的邻居，并更新它们的临时距离为更小
            updateDist(vertex);
            // 前顶点的邻居处理完成后，把它从未访问集合中删除
            graph.remove(vertex);
            vertex.setVisited(true);
        }

        for (Vertex vertex : vertexList) {
            System.out.println(vertex.getName() + (vertex.getPerv() == null? "null":vertex.getPerv().getName()));
        }
    }


    private static void updateDist(Vertex vertex) {
        List<Edge> edges = vertex.getEdges();
        for (Edge edge : edges) {
            Vertex linked = edge.getLinked();
            if (!linked.isVisited()) {
                int weight = edge.getWeight();
                if (weight < linked.getDist()){
                    linked.setDist(weight);
                    linked.setPerv(vertex);
                }
            }
        }
    }

    private static Vertex findMinVertex(List<Vertex> graph) {
        Vertex min = graph.get(0);
        for (int i = 1; i < graph.size(); i++) {
            Vertex vertex = graph.get(i);
            if (vertex.getDist() < min.getDist()){
                min = vertex;
            }
        }
        return min;
    }
}
